SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Factorial code</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Factorial code</span></span>

</h1>

</header>

<p>Most real world data sets consist of data vectors whose individual components are not <a href="Statistically_independent" class="mw-redirect" title="Statistically independent">statistically independent</a>. In other words, knowing the value of an element will provide information about the value of elements in the data vector. When this occurs, it can be desirable to create a <b>factorial code</b> of the data, i.e., a new vector-valued <a href="Representation_(mathematics)" title="Representation (mathematics)">representation</a> of each data vector such that it gets uniquely encoded by the resulting code vector (loss-free coding), but the code components are statistically independent.

</p><p>Later <a href="Supervised_learning" title="Supervised learning">supervised learning</a> usually works much better when the raw input data is first translated into such a factorial code. For example, suppose the final goal is to classify images with highly redundant pixels. A <a href="Naive_Bayes_classifier" title="Naive Bayes classifier">naive Bayes classifier</a> will assume the pixels are <a href="Statistically_independent" class="mw-redirect" title="Statistically independent">statistically independent</a> <a href="Random_variables" class="mw-redirect" title="Random variables">random variables</a> and therefore fail to produce good results. If the data are first encoded in a factorial way, however, then the naive Bayes classifier will achieve its <a href="Global_optimum" class="mw-redirect" title="Global optimum">optimal</a> performance (compare Schmidhuber et al. 1996).

</p><p>To create factorial codes, <a href="Horace_Barlow" title="Horace Barlow">Horace Barlow</a> and co-workers suggested to minimize the sum of the <a href="Bit" title="Bit">bit</a> entropies of the code components of <a href="Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary</a> codes (1989). <a href="J%C3%BCrgen_Schmidhuber" title="Jürgen Schmidhuber">Jürgen Schmidhuber</a> (1992) re-formulated the problem in terms of predictors and binary <a href="Feature_(machine_learning)" title="Feature (machine learning)">feature</a> <a href="Detectors" class="mw-redirect" title="Detectors">detectors</a>, each receiving the raw data as an input. For each detector there is a predictor that sees the other detectors and learns to predict the output of its own detector in response to the various input vectors or images. But each detector uses a <a href="Machine_learning" title="Machine learning">machine learning</a> algorithm to become as unpredictable as possible. The <a href="Global_optimum" class="mw-redirect" title="Global optimum">global optimum</a> of this <a href="Objective_function" class="mw-redirect" title="Objective function">objective function</a> corresponds to a factorial code represented in a distributed fashion across the outputs of the feature detectors.

</p><p>Painsky, Rosset and Feder (2016, 2017) further studied this problem in the context of <a href="Independent_component_analysis" title="Independent component analysis">independent component analysis</a> over finite alphabet sizes. Through a series of theorems they show that the factorial coding problem can be accurately solved with a branch and bound search tree algorithm, or tightly approximated with a series of linear problems. In addition, they introduce a simple transformation (namely, order permutation) which provides a greedy yet very effective approximation of the optimal solution. Practically, they show that with a careful implementation, the favorable properties of the order permutation may be achieved in an asymptotically optimal computational complexity. Importantly, they provide theoretical guarantees, showing that while not every random vector can be efficiently decomposed into independent components, the majority of vectors do decompose very well (that is, with a small constant cost), as the dimension increases. In addition, they demonstrate the use of factorial codes to data compression in multiple setups (2017).

</p>

<ul><li><a href="Blind_signal_separation" class="mw-redirect" title="Blind signal separation">Blind signal separation (BSS)</a></li>

<li><a href="Principal_component_analysis" title="Principal component analysis">Principal component analysis (PCA)</a></li>

<li><a href="Factor_analysis" title="Factor analysis">Factor analysis</a></li>

<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>

<li><a href="Image_processing" class="mw-redirect" title="Image processing">Image processing</a></li>

<li><a href="Signal_processing" title="Signal processing">Signal processing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><a href="Horace_Barlow" title="Horace Barlow">Horace Barlow</a>, T. P. Kaushal, and G. J. Mitchison. Finding minimum entropy codes. Neural Computation, 1:412-423, 1989.</li>

<li><a href="J%C3%BCrgen_Schmidhuber" title="Jürgen Schmidhuber">Jürgen Schmidhuber</a>. Learning factorial codes by predictability minimization. Neural Computation, 4(6):863-879, 1992</li>

<li>J. Schmidhuber and M. Eldracher and B. Foltin. Semilinear predictability minimization produces well-known feature detectors. Neural Computation, 8(4):773-786, 1996</li>

<li>A. Painsky, S. Rosset and M. Feder. Generalized independent component analysis over finite alphabets. IEEE Transactions on Information Theory, 62(2):1038-1053, 2016</li>

<li>A. Painsky, S. Rosset and M. Feder. Large Alphabet Source Coding using Independent Component Analysis. IEEE Transactions on Information Theory, 63(10):6514 - 6529, 2017</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-06-24" href="https://en.wikipedia.org/wiki/?title=Factorial_code&oldid=1161662877">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>